
"""
538. 把二叉搜索树转换为累加树
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.nums = 0

    """
    利用二叉搜索的中序遍历，将升序调整为降序，维护个变量，累加便利的结果，该结果即为当前节点的新值
    """
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.traverse(root)
        return root

    '''遍历二叉树'''
    def traverse(self, root: Optional[TreeNode]):
        if not root:
            return
        # 前序位置
        self.traverse(root.right)
        # 中序位置
        self.nums = self.nums + root.val
        root.val = self.nums
        self.traverse(root.left)
        # 后序位置